package com.base.dp;

/**
 * 给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
 * <p>
 * 请你返回让 s 成为回文串的 最少操作次数 。
 * <p>
 * 「回文串」是正读和反读都相同的字符串。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "zzazz"
 * 输出：0
 * 解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
 * 示例 2：
 * <p>
 * 输入：s = "mbadm"
 * 输出：2
 * 解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
 * 示例 3：
 * <p>
 * 输入：s = "leetcode"
 * 输出：5
 * 解释：插入 5 个字符后字符串变为 "leetcodocteel"
 * 提示：
 * <p>
 * 1 <= s.length <= 500
 * s 中所有字符都是小写字母。
 */
public class MinInsertions {
    public static void main(String[] args) {
        MinInsertions m = new MinInsertions();
        System.out.println(m.minInsertions("leetcode"));
    }

    /**
     * 定义 dp[i][j] 为使字符串 s 的子串 s[i...j] 成为回文串所需的最少插入次数。我们的目标是求出 dp[0][n-1]，其中 n 是字符串 s 的长度。
     *
     * @param s
     * @return
     */
    public int minInsertions(String s) {
        int n = s.length();
        //定义 dp[i][j] 为使字符串 s 的子串 s[i...j] 成为回文串所需的最少插入次数。
        // 我们的目标是求出 dp[0][n-1]，其中 n 是字符串 s 的长度。
        int[][] dp = new int[n][n];
        //从后往前遍历，保证子问题已经解决，这个怎么理解
        for (int i = n - 2; i >= 0; i--) {  // leetcode
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) { // i = n-2 j = n-1
                    dp[i][j] = dp[i + 1][j - 1];  //dp[n-2][n-1]=dp[n-1][n-2]
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1; // dp[n-2][n-1] = dp[n-1][n-1]  || dp[n-2][n-2]  + 1
                }
            }
        }

        return dp[0][n - 1];
    }
}
